package solution;

import java.util.Stack;

class Solution {
    /**
     * 415字符串相加
     * https://leetcode.cn/problems/add-strings/
     * @param num1
     * @param num2
     * @return
     */
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        //记录进位的变量
        int carry = 0;
        //记录字符串的下标
        int n1 = num1.length() - 1;
        int n2 = num2.length() - 1;
        for(; n1 >= 0 || n2 >= 0 || carry != 0; n1--, n2--) {
            int c1 = (n1 < 0) ? 0 : (num1.charAt(n1) - '0');
            int c2 = (n2 < 0) ? 0 : (num2.charAt(n2) - '0');
            sb.append((c1 + c2 + carry) % 10);
            carry = (c1 + c2 + carry) / 10;
        }
        //翻转字符串
        return sb.reverse().toString();
    }

    /**
     * 20有效括号匹配
     * https://leetcode.cn/problems/valid-parentheses/
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char x : s.toCharArray()) {
            if(x == '(') {
                stack.push(')');
            } else if(x == '[') {
                stack.push(']');
            } else if(x == '{') {
                stack.push('}');
            } else if(stack.empty() || stack.pop() != x) {
                return false;
            }
        }
        return stack.empty();
    }
    /**
     * 461汉明距离
     * https://leetcode.cn/problems/hamming-distance/
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance(int x, int y) {
        int count = 0;
        for(int c = x ^ y; c != 0; c &= (c - 1)) {
            count++;
        }
        return count;
    }
}